划分序列

Time Limit: 20 Sec Memory Limit: 256 MB

Description

给定一个长度为n的序列A;，现在要求把这个序列分成恰好K段(每一段是一个连续子序列，且每个元素恰好属于一段)，并且每段至少有一个元素，使得和最大的那一段的和最小。
请你求出这个最小值。

Input

第一行两个正整数n,K，意义见题目描述。接下来一行n个整数表示序列Ai

Output

仅一行一个整数表示答案。

Sample Input

9 4
　　1 1 1 3 2 2 1 3 1

Sample Output

5

HINT

img

Main idea

将序列分为若干段，使得和最大的那一段最小，值可以为负。

Source

首先，显然都想到了二分答案。

我们先把都为正数或负数的情况写了：Ai>=0的时候求出最小的划分段数x，若x<=K则表示当前答案可行；Ai<=0的时候求出最大的划分段数x，若x>=K则表示当前答案可行。然后再打了暴力，接着我们对拍一下，惊讶地发现了一个规律：若最小划分段数为L，最大划分段数为R，当L<=K<=R时则可以更新。

然后我们用DP来求L和R，也就是：若一段的和满足<=mid，则可以分为一段。

然后我们发现，可以用线段树优化寻找1~i-1中的最小值或最大值，这样判断就可以满足效率了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int INF = 2147483640;
const int ONE = 5e4+5;

int n,block;
int L,R;
int x,sum[ONE],s[ONE];
int li[ONE],li_num;
int f_min[ONE],f_max[ONE];
int res_min,res_max;
int Zero;

int get()
{
    int res=1,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

namespace Seg
{
    struct power
    {
        int minn;
        int maxx;
    }Node[ONE];

    void Build(int i,int l,int r)
    {
        Node[i].minn = INF;
        Node[i].maxx = -INF;
        if(l==r) return;
        int mid=(l+r)>>1;
        Build(i<<1,l,mid);    Build(i<<1|1,mid+1,r);
    }

    void Update(int i,int l,int r,int L,int x,int PD)
    {
        if(l==r)
        {
            if(!PD) Node[i].minn = x;
            else Node[i].maxx = x;
            return;
        }
        int mid=(l+r)>>1;
        if(L<=mid) Update(i<<1,l,mid,L,x,PD);
        else Update(i<<1|1,mid+1,r,L,x,PD);
        Node[i].minn = min(Node[i<<1].minn, Node[i<<1|1].minn);
        Node[i].maxx = max(Node[i<<1].maxx, Node[i<<1|1].maxx);
    }

    void Query(int i,int l,int r,int L,int R)
    {
        if(L<=l && r<=R)
        {
            res_min=min(res_min, Node[i].minn);
            res_max=max(res_max, Node[i].maxx);
            return;
        }
        int mid=(l+r)>>1;
        if(L<=mid) Query(i<<1,l,mid,L,R);
        if(mid+1<=R) Query(i<<1|1,mid+1,r,L,R);
    }
}

int Check(int mid)
{
    Seg::Build(1,1,li_num);
    Seg::Update(1,1,li_num, Zero,0,0);
    Seg::Update(1,1,li_num, Zero,0,1);
    for(int i=1;i<=n;i++)
    {
        int pos = lower_bound(li+1,li+li_num+1,sum[i] - mid) - li;
        res_min = INF;    res_max = -INF;    Seg::Query(1,1,li_num, 1,pos);
        f_min[i] = res_min + 1;
        f_max[i] = res_max + 1;
        Seg::Update(1,1,li_num, s[i],f_min[i],0);
        Seg::Update(1,1,li_num, s[i],f_max[i],1);
    }
    return (f_min[n]<=block && block<=f_max[n]);
}


int main()
{
    n=get();    block=get();
    li[++li_num] = 0;
    for(int i=1;i<=n;i++)
    {
        x=get();
        li[++li_num] = sum[i] = sum[i-1] + x;
        if(x < 0) L+=x; else R+=x;
    }

    sort(li+1,li+li_num+1);
    li_num = unique(li+1,li+li_num+1) - li - 1;

    for(int i=1;i<=n;i++)
        s[i]=lower_bound(li+1,li+li_num+1, sum[i]) - li;
    Zero = lower_bound(li+1,li+li_num+1, 0) - li;

    while(L < R - 1)
    {
        int mid=(L+R)>>1;
        if(Check(mid)) R = mid;
        else L = mid;
    }

    if(Check(L)) printf("%d",L);
    else printf("%d",R);
}